package offer.leetcode.easy;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 数组中重复的数字
 * https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 * 总结：
 *     1、注意数组中数字与下标的关系
 *     2、利用合适的结构，如本题的set
 *
 * @author DengYuan2
 * @create 2021-01-04 19:31
 */
public class E_03 {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 0, 2, 5, 3};
//        int repeatNumber = findRepeatNumber1(arr);
//        System.out.println(repeatNumber);
        int repeatNumber2 = findRepeatNumber2(arr);
        System.out.println(repeatNumber2);


    }

    /**
     * 我的写法，较差
     * @param nums
     * @return
     */
    public static int findRepeatNumber1(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(16);
        int res = -1;
        for (int i = 0; i < nums.length; i++) {
            Integer count = map.getOrDefault(nums[i], 0);
            if (count >= 1) {
                res = nums[i];
                break;
            } else {
                map.put(nums[i], count + 1);
            }
        }
        return res;
    }

    /**
     * 原地置换
     * 写法1：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/yuan-di-zhi-huan-shi-jian-kong-jian-100-by-derrick/
     * 写法2：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/
     * 个人觉得写法2更好一些
     * @param nums
     * @return
     */
    public static int findRepeatNumber2(int[] nums) {
        //写法1：
//        int tmp = -1;
//        for (int i = 0; i < nums.length; i++) {
//            while (nums[i] != i) {
//                //若它应该在的位置已经有和它一样的值，则返回它
//                if (nums[i]==nums[nums[i]]){
//                    return nums[i];
//                }
//                tmp = nums[i];
//                nums[i] = nums[nums[i]];
//                nums[tmp] = tmp;
//            }
//        }
//        return -1;

        //写法2：
        int tmp =-1;
        int i=0;
        while (i<nums.length){
            if (i==nums[i]){
                i++;
                continue;
            }
            if (nums[i]==nums[nums[i]]){
                return nums[i];
            }
            tmp =nums[i];
            nums[i]=nums[tmp];
            nums[tmp] =tmp;
        }
        return -1;

    }

    /**
     * 哈希表/Set
     * @param nums
     * @return
     */
    public static int findRepeatNumber3(int[] nums){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                return nums[i];
            }else {
                set.add(nums[i]);
            }
        }
        return -1;
    }

    /**
     * 使用临时数组
     * @param nums
     * @return
     */
    public static int findRepeatNumber4(int[] nums){
        int[] tmp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tmp[nums[i]]++;
            if (tmp[nums[i]]>1){
                return nums[i];
            }
        }
        return -1;
    }
}
